/**
 * Written By: MinHo Kim (minho.kim.korea@gmail.com)
 * Copyright (C) 2011, MinHo Kim, Software Expert Program, KAIST University, Seoul, Korea.
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public License as published 
 * by the Free Software Foundation; version 2 of the License.
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 * See the GNU General Public License for more details.
 */
package kaist.sep502.tsp.algorithm.search;

import kaist.sep502.tsp.algorithm.heuristic.GreedySearchHeuristic;
import kaist.sep502.tsp.algorithm.heuristic.Heuristic;
import kaist.sep502.tsp.model.CityPath;
import kaist.sep502.tsp.model.Problem;
import kaist.sep502.tsp.model.Solution;

/**
 * @author minho kim
 * 
 */
public class AStarSearch extends SearchAlgorithm {

	/**
	 * @param problem
	 */
	public AStarSearch(Problem problem) {
		super(problem);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see kaist.sep502.tsp.algorithm.search.SearchAlgorithm#search()
	 */
	@Override
	public Solution search() {
		solution = new Solution("A*");
		solution.expandedNodeCount = 0;
		solution.startStopWatch();

		CityPath cityPath = new CityPath(problem, problem.departureCityNo);
		setHeuristicAlgorithm(new GreedySearchHeuristic());
		Heuristic heuristic;
		try {
			// for(int i=0; i<problem.getCitySize()+1; i++){
			for (int i = 0; i < problem.citySize; i++) { // i는 cityNo가 아니며,
															// 무한반복을 막기 위해 사용됨.
				heuristic = heuristicAlgorithm.getHx(problem, cityPath);
				cityPath.moveTo(problem, heuristic.cityNo, heuristic.hx);

				if (problem.checkGoal(cityPath)) {
					solution.setGoalCityPath(cityPath);
					solution.setSuccess(true);
					solution.stopStopWatch();
					solution.expandedNodeCount = heuristicAlgorithm.getExpandedCount();
					return solution;
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
		
		return solution;
	}
}
